package cn.edu.jxau.test;

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.DataInputStream;
import java.io.DataOutputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.Objects;

/**
 * 外部排序
 * 
 * 利用下面的代码，事先生成大规模数据
 * DataOutputStream out = new DataOutputStream(new FileOutputStream("C:\\Users\\PC-Clive\\Desktop\\data.dat"));
 * for(int i=0;i<100000;i++) {
 *     out.writeInt((int)(Math.random()*50000));
 * }
 * out.close();
 * 
 * @author 付大石
 */
public class Sort {

    public static void main(String[] args) throws IOException {

        File sourceFile = new File("C:\\Users\\PC-Clive\\Desktop\\data.dat");
        File targetFile = new File("C:\\Users\\PC-Clive\\Desktop\\target.dat");
        display(sourceFile);
        sort(sourceFile, targetFile, 100);
        display(targetFile);
    }

    private static void display(File file) throws IOException {

        // 参数校验 //
        Objects.requireNonNull(file, "参数file不能为null");

        // 读取文件 //
        StringBuilder builder = new StringBuilder();
        try (FileInputStream fileIn = new FileInputStream(file); DataInputStream in = new DataInputStream(fileIn)) {
            builder.append("[");
            for (int i = 0; i < 1000 && in.available() > 0; i++) {
                builder.append(in.readInt()).append(",");
            }
            if (builder.length() > 2) { // 删除逗号
                builder.deleteCharAt(builder.length() - 1);
            }
            builder.append("]");
        } catch (IOException ex) {
            throw new IOException("文件读取失败", ex);
        }
        System.out.println(builder.toString());
    }

    /**
     * 外部排序
     * @param sourcefile
     * @param targetFile
     * @param MAX_ARRAY_LEN 可开辟的最大数组长度
     * @throws IOException 
     */
    private static void sort(File sourceFile, File targetFile, final int MAX_ARRAY_LEN) throws IOException {

        final File tempFile1 = new File("f1.dat");
        final File tempFile2 = new File("f2.dat");
        final File tempFile3 = new File("f3.dat");
        int segmentNum = init(MAX_ARRAY_LEN, sourceFile, tempFile1);
        System.out.println("segmentNum:" + segmentNum);
        merge(segmentNum, MAX_ARRAY_LEN, tempFile1, tempFile2, tempFile3, targetFile);
    }

    /**
     * 
     * @param segmentSize 分段大小
     * @param sourceFile 
     * @param tempFile 创建的临时文件，其中每个分段有序
     * @return 分段数量
     * @throws IOException 
     */
    private static int init(int segmentSize, File sourceFile, File tempFile) throws IOException {

        int[] arr = new int[segmentSize];
        int segmentCounter = 0;
        try (FileInputStream fileIn = new FileInputStream(sourceFile);
                BufferedInputStream bufferedIn = new BufferedInputStream(fileIn);
                DataInputStream in = new DataInputStream(bufferedIn);
                FileOutputStream fileOut = new FileOutputStream(tempFile);
                BufferedOutputStream bufferedOut = new BufferedOutputStream(fileOut);
                DataOutputStream out = new DataOutputStream(bufferedOut)) {
            while (in.available() > 0) {
                segmentCounter++;
                int i = 0;
                for (; in.available() > 0 && i < segmentSize; i++) { // 分段
                    arr[i] = in.readInt();
                }
                innerSort(arr, 0, i); // 对分段进行排序
                for (int j = 0; j < i; j++) {
                    out.writeInt(arr[j]);
                }
            }
        } catch (IOException ex) {
            throw new IOException("分段初始化失败", ex);
        }
        return segmentCounter;
    }

    /**
     * 对分段进行排序，可以使用任何排序算法，这里使用简单的插入排序
     * @param arr
     * @param start
     * @param end
     */
    private static void innerSort(int[] arr, int start, int end) {

        for (int i = start + 1; i < end; i++) {
            int j = i;
            int temp = arr[j];
            while (j > start && temp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                j--;
            }
            arr[j] = temp;
        }
    }

    private static void merge(int segmentNum, int segmentSize, File f1, File f2, File f3, File targetFile)
            throws IOException {

        if (segmentNum > 1) { // f1中有多个分段，继续归并
            mergeSegment(segmentNum, segmentSize, f1, f2, f3);
            merge((segmentNum + 1) / 2, segmentSize * 2, f3, f1, f2, targetFile);
        } else { // segmentNum == 1,f1中仅一个分段，排序完成
            if (targetFile.exists()) {
                targetFile.delete();
            }
            f1.renameTo(targetFile);
        }
    }

    private static void mergeSegment(int segmentNum, int segmentSize, File f1, File f2, File f3) throws IOException {

        try (FileInputStream fileIn1 = new FileInputStream(f1);
                BufferedInputStream bufferedIn1 = new BufferedInputStream(fileIn1);
                DataInputStream in1 = new DataInputStream(bufferedIn1);) {

            // 将f1中前半部分的segment放入f2 //
            try (FileOutputStream fileOut2 = new FileOutputStream(f2);
                    BufferedOutputStream bufferedOut2 = new BufferedOutputStream(fileOut2);
                    DataOutputStream out2 = new DataOutputStream(bufferedOut2)) {
                int len = segmentNum / 2 * segmentSize;
                for (int i = 0; i < len; i++) {
                    out2.writeInt(in1.readInt());
                }
            } catch (IOException e) {
                throw new IOException("分半失败", e);
            }

            // f1，f2归并，归并结果输入到f3中 //
            try (FileInputStream fileIn2 = new FileInputStream(f2);
                    BufferedInputStream bufferedIn2 = new BufferedInputStream(fileIn2);
                    DataInputStream in2 = new DataInputStream(bufferedIn2);

                    FileOutputStream fileOut3 = new FileOutputStream(f3);
                    BufferedOutputStream bufferedOut3 = new BufferedOutputStream(fileOut3);
                    DataOutputStream out3 = new DataOutputStream(bufferedOut3)) { // 后面要用到in1、in2、out3

                for (int i = 0; i < segmentNum / 2; i++) {
                    mergeSegment(segmentSize, in1, in2, out3);
                }

                // 处理f1中多余的字段 //
                while (in1.available() > 0) {
                    out3.writeInt(in1.readInt());
                }
            } catch (IOException e) {
                throw new IOException("归并失败", e);
            }
        } catch (IOException e) {
            throw new IOException("归并失败", e);
        }
    }

    private static void mergeSegment(int segmentSize, DataInputStream in1, DataInputStream in2, DataOutputStream out)
            throws IOException {

        int fromIn1 = in1.readInt();
        int fromIn2 = in2.readInt();
        int in1Count = 1;
        int in2Count = 1;
        while (true) {

            if (fromIn1 < fromIn2) {
                out.writeInt(fromIn1);
                if (in1.available() == 0 || in1Count >= segmentSize) {
                    out.writeInt(fromIn2);
                    break;
                }
                fromIn1 = in1.readInt();
                in1Count++;
            } else {
                out.writeInt(fromIn2);
                if (in2.available() == 0 || in2Count >= segmentSize) {
                    out.writeInt(fromIn1);
                    break;
                }
                fromIn2 = in2.readInt();
                in2Count++;
            }
        }

        while (in1.available() > 0 && in1Count < segmentSize) {
            out.writeInt(in1.readInt());
            in1Count++;
        }
        while (in2.available() > 0 && in2Count < segmentSize) {
            out.writeInt(in2.readInt());
            in2Count++;
        }
    }
}